package com.lwl.Algorithmic_data_structure.归并排序.mycode;

/**
 * 求数组中逆序对的个数
 */
public class ReversePair {

    public static int reversePair(int[] array)
    {
        if (array == null || array.length < 2)
        {
            return 0;
        }

        return process(array, 0, array.length - 1);
    }

    private static int process(int[] array, int left, int right)
    {
        if (left >= right)
        {
            return 0;
        }

        int mid = left + ((right - left) >> 2);

        return process(array, left, mid)
                + process(array, mid + 1, right)
                + merge(array, left, mid, right);
    }

    private static int merge(int[] array, int left, int mid, int right)
    {
        int[] help = new int[right - left + 1];
        int index = help.length - 1;
        int l = mid;
        int r = right;
        int res = 0;

        while (l >= left && r >= mid + 1)
        {
            if (array[l] > array[r])
            {
                res += r - mid;
                help[index--] = array[l--];
            }
            else
            {
                help[index--] = array[r--];
            }
        }

        while (l >= left)
        {
            help[index--] = array[l--];
        }
        while (r >= mid + 1)
        {
            help[index--] = array[r--];
        }

        for (int i = 0; i < help.length; i++) {
            array[left + i] = help[i];
        }

        return res;
    }

}
